package Easy;

import java.util.*;

public class Solution720 {
    public static void main(String[] args) {
        String[] words = new String[]{"ogz","eyj","e","ey","hmn","v","hm","ogznkb","ogzn","hmnm","eyjuo","vuq","ogznk","og","eyjuoi","d"};
        String[] words2 = new String[]{"yo","ew","fc","zrc","yodn","fcm","qm","qmo","fcmz","z","ewq","yod","ewqz","y"};
        String[] words3 = new String[]{"a","banana","app","appl","ap","apply","apple"};
        String s = longestWord(words);
        String s2 = longestWord(words2);
        String s3 = longestWord(words3);
        System.out.println(s);
        System.out.println(s2);
        System.out.println(s3);
    }
    public static String longestWord(String[] words) {
        if(words.length==0)
            return "";
        Map<Integer, Set<String>> map = new HashMap<Integer,Set<String>>();
        for(String s:words){
            int length = s.length();
            if(map.containsKey(length)){
                Set<String> set = map.get(length);
                set.add(s);
            }else{
                Set<String> set = new TreeSet<String>(new Comparator<String>() {
                    @Override
                    public int compare(String o1, String o2) {
                        return o1.compareTo(o2);
                    }
                });
                set.add(s);
                map.put(length,set);
            }
        }
        if(!map.containsKey(1))
            return "";
        int i;
        for(i = 1 ; i <=30; i++){
            if(!map.containsKey(i)){
                break;
            }
        }
        int res = 0;
        for(int j = 2 ; j < i ; j++){
            Set<String> set = map.get(j);
            Set<String> setPre = map.get(j-1);
            List<String> deleteList = new ArrayList<String>();
            for(String str:set){
                String s = str.substring(0,j-1);
                boolean b = false;
                for(String pre : setPre){
                    if(pre.equals(s)){
                        b = true; // 可以保存
                        break;
                    }
                }
                if(!b){
                    // set.remove(str); 会报错java.util.ConcurrentModificationException 因为不能一边遍历一边删除
                    // 先加入到待删除集合中，等遍历完set以后，再从set里删除这些
                    deleteList.add(str);

                }
            }
            for(String str : deleteList) {
                Iterator<String> iterator = set.iterator();
                while (iterator.hasNext()) {
                    String check = iterator.next();
                    if (check.equals(str)) {
                        iterator.remove();
                    }
                }
            }
            if(set.size() == 0){
                res = j-1;
                break;
            }
        }
        Set<String> set = map.get(res==0?i-1:res);
        // 找出字典序最小的单词
        //
        for(String s : set){
            return s;
        }
        return "";

    }
}
